#include<stdio.h>
/*
 *
	堆排序：
	1. 将原始数组构造成大顶堆
	2. 循环（将大顶堆的根节点与末尾节点交换，堆元素减1）
	3. 直到大顶堆只剩一个元素时，终止循环

	基本规则：元素下标从0开始
	1. 若当前节点的元素下标为i, 则左子节点下标为 2 * i + 1 ； 右子节点下标为 2 * i + 2;
	2. 若当前节点的元素下标为i, 则父节点的下标为 (i - 1) / 2;
	3. 完全二叉树的非叶子节点的下标 <= (末尾元素索引 - 1) / 2;

	测试案例：
	before data : 1 5 3 4 2 0
	After data : 0 1 2 3 4 5 
 */

/*
 * 	data:待排数组
 * 	start: 节点索引
 * 	end: 堆的最后一个元素索引（用于控制是否越界）
 * 	对data[start] 为根节点的二叉树进行堆排序
 */

void heapsort(int * data, int start, int endIndex);
/*
 *
	对data[i] 与 data[j] 交换位置
 */
void swap(int * data, int i, int j);
int main(){

	int data[] = {1, 5, 3, 4, 2, 0};
	//打印原始数组
	printf("before data : ");
	int length = sizeof(data) / sizeof(int);
	for(int i = 0; i < length; i++){
		printf("%d ", data[i]);
	}
	printf("\n");
	//堆排序
	//1. 将原始数组构造成大顶堆，从最后一个非叶子节点开始从右到左，从下到上
	int noleafIndex = (length - 1 - 1) / 2;
	while(noleafIndex >= 0){
		heapsort(data, noleafIndex, length - 1);
		noleafIndex--;
	}

	//2. 循环（将大顶堆的根节点与末尾节点交换，堆元素减1,直到数组中只有一个元素
	int endIndex = length -1;
	while(endIndex > 0){
		swap(data, 0, endIndex);
		endIndex--;
		heapsort(data, 0, endIndex);
	}
	
	//打印排序数组
	printf("After data : ");
	int length1 = sizeof(data) / sizeof(int);
	for(int i = 0; i < length1; i++){
		printf("%d ", data[i]);
	}
	printf("\n");
}

void heapsort(int * data, int start, int endIndex){
	int leftIndex = 2 * start + 1;
	if(leftIndex > endIndex){
		//左子节点已经越界：证明是叶子节点，无需堆排序
		return;
	}
	int rightIndex = 2 * start + 2;
	int maxIndex = leftIndex;
	//若果有右子节点且比左子节点大，则更新maxIndex
	if(rightIndex <= endIndex && data[rightIndex] > data[leftIndex]){
		maxIndex = rightIndex;
	}
	//比较当前节点data[start]与最大子节点data[maxIndex],若小于子节点，则更新当前节点
	if(data[start] < data[maxIndex]){
		swap(data, start, maxIndex);
		heapsort(data, maxIndex, endIndex);
	}
}

void swap(int * data, int i, int j){
	int tmp;
	tmp = data[i];
	data[i] = data[j];
	data[j] = tmp;
}




